/*
 * ---------------------------------------------------------------------
 * Copyright (c) 2014, 2015 All Right Reserved
 * This software is developed for study and improve coding skill ...
 *
 * Project:  Excellent Coding < EC >
 *
 * ecMap.h
 * This software define all the EC map interface.
 * Eamil:  epengao@126.com
 * Author: Peter Gao
 * Version: First initinal version.
 * --------------------------------------------------------------------
 */

#ifndef EC_MAP_H
#define EC_MAP_H

#include "ecNode.h"
#include "ecBaseType.h"
#define MAP_DEFAULT_SIZE         1024

namespace ec {

template<typename KeyT, typename ValT>
class ecMap
{
public:
    ecMap();
    virtual ~ecMap();
    virtual void ResetMap();
    virtual EC_U32 AddToMap(const KeyT* pKey, const ValT* pVal);
    virtual EC_U32 DeleteFromMap(const KeyT* pKey);
    virtual EC_U32 SearchFromMap(const KeyT* pKey, ValT* pVal) const;

protected:
    virtual EC_S32 FindInsertPos(const KeyT* pKey) const;
    virtual EC_U32 InserToMapPos(const KeyT* pKey, 
                                 const ValT* pVal, EC_U32 nPos);

protected:
    EC_U32                  m_nSize;
    EC_U32                  m_nItemCount;
    ecPairNode<KeyT,ValT>*  m_pDataSet;
};

/* **************** implementation *******************/

template<typename KeyT, typename ValT>
ecMap<KeyT, ValT>::ecMap()
:m_nSize(MAP_DEFAULT_SIZE)
,m_nItemCount(0)
,m_pDataSet(EC_NULL)
{
    m_pDataSet = new ecPairNode<KeyT,ValT>[m_nSize];
}

template<typename KeyT, typename ValT>
ecMap<KeyT, ValT>::~ecMap()
{
    if(m_pDataSet)
        delete []m_pDataSet;
}

template<typename KeyT, typename ValT>
void ecMap<KeyT, ValT>::ResetMap()
{
    m_nItemCount = 0;
}

template<typename KeyT, typename ValT>
EC_U32 ecMap<KeyT, ValT>::AddToMap(const KeyT *pKey, 
                                                        const ValT *pVal)
{
    if(EC_NULL == m_pDataSet)
        return EC_Err_Memory_Overflow;
    if((EC_NULL == pKey) || (EC_NULL == pVal))
        return EC_Err_BadParam;

    EC_U32 nRet = EC_Err_None;
    EC_S32 nPos = FindInsertPos(pKey);
    if(nPos >= 0)
    {
        nRet = InserToMapPos(pKey, pVal, nPos);
    }
    else
        nRet = EC_Err_DataAlreadyExist;

    return nRet;
}

template<typename KeyT, typename ValT>
EC_U32 ecMap<KeyT, ValT>::DeleteFromMap(const KeyT *pKey)
{
    EC_U32 nPos = 0;
    for(; nPos < m_nItemCount; ++nPos)
    {
        if(m_pDataSet[nPos].m_sKey == *pKey)
        {
            for(EC_U32 i = nPos; i < m_nItemCount-1; ++i)
                m_pDataSet[i] = m_pDataSet[i+1];
            m_nItemCount--;
            return EC_Err_None;
        }
    }

    return EC_Err_DataNotExist;
}

template<typename KeyT, typename ValT>
EC_U32 ecMap<KeyT, ValT>::SearchFromMap(
                                               const KeyT *pKey, ValT *pVal) const
{
    EC_U32 nStart = 0;
    EC_U32 nEnd   = m_nItemCount;
    EC_U32 nMid   = (nStart + nEnd)/2;
    while (nStart <= nEnd)
    {
        if (m_pDataSet[nMid].m_sKey == *pKey)
        {
            *pVal = m_pDataSet[nMid].m_sVal;
            return EC_Err_None;
        }
        else if(m_pDataSet[nMid].m_sKey < *pKey)
            nStart = nMid+1;
        else if(m_pDataSet[nMid].m_sKey > *pKey)
            nEnd = nMid-1;
        nMid = (nStart + nEnd)/2;
    }

    return EC_Err_DataNotExist;
}

template<typename KeyT, typename ValT>
EC_S32 ecMap<KeyT, ValT>::FindInsertPos(
                                               const KeyT *pKey) const
{
    if(0 == m_nItemCount)
        return 0;

    EC_U32 i = 0;
    for(; i < m_nItemCount; ++i)
        if(*pKey < m_pDataSet[i].m_sKey)
            break;

    return i;
}

template<typename KeyT, typename ValT>
EC_U32 ecMap<KeyT, ValT>::InserToMapPos(
                                               const KeyT *pKey, 
                                               const ValT *pVal, EC_U32 nPos)
{
    if(nPos > m_nItemCount)
        return EC_Err_BadParam;

    if(m_nItemCount >= m_nSize)
    {
        ecPairNode<KeyT, ValT>* pTmp = m_pDataSet;
        EC_U32 nNewSize = m_nSize + MAP_DEFAULT_SIZE;
        m_pDataSet = new ecPairNode<KeyT, ValT>[nNewSize];
        if(m_pDataSet)
        {
            memcpy(m_pDataSet, pTmp, sizeof(ecPairNode<KeyT, ValT>)*m_nSize);
            m_nSize = nNewSize;
        }
        else
        {
            m_pDataSet = pTmp;
            return EC_Err_Memory_Overflow;
        }
    }

    for(EC_U32 i = m_nItemCount; i > nPos; --i)
        m_pDataSet[i] = m_pDataSet[i-1];

    m_pDataSet[nPos].m_sKey = *pKey;
    m_pDataSet[nPos].m_sVal = *pVal;
    m_nItemCount++;

    return EC_Err_None;
}
} /* namespace ec */
#endif /* EC_MAP_H */